//#include<bits/stdc++.h>
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

const int INF = INT_MAX;
typedef pair<int, int> PII;

struct Edge {
	int to, next, weight;
}e[105];
int cnt = 0;
int head[105] = { 0 };
int n, m, s;
long long dis[10005];
bool vis[10005] = { 0 };

void addEdge(int u, int v, int w) {
	e[++cnt].to = v;
	e[cnt].weight = w;
	e[cnt].next = head[u];
	head[u] = cnt;
}

void dijkstra() {
	for (int i = 1;i <= n;i++)
		dis[i] = INF;
	dis[s] = 0;
	priority_queue<PII, vector<PII>, greater<PII>> pq;
	pq.push({ 0,s });
	while (!pq.empty()) {
		int u = pq.top().second;
		pq.pop();
		if (vis[u])
			continue;
		vis[u] = true;
		for (int i = head[u];i > 0;i = e[i].next) {
			int j = e[i].to;
			if (dis[j] > dis[u] + e[i].weight)
				dis[j] = dis[u] + e[i].weight, pq.push({ dis[j] ,j });
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m >> s;
	for (int i = 0;i < m;i++) {
		int u, v, w;
		cin >> u >> v >> w;
		addEdge(u, v, w);
	}
	dijkstra();
	for (int i = 1;i <= n;i++)
		cout << dis[i] << " ";
	return 0;
}

//5 6 1
//1 2 2
//2 3 2
//2 4 1
//1 3 5
//3 4 3
//1 4 4

